{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #秋叶收藏集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #秋叶收藏集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 `leaves`， 字符串 `leaves` 仅包含小写字符 `r` 和 `y`， 其中字符 `r` 表示一片红叶，字符 `y` 表示一片黄叶。\r\n",
    "出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`leaves = \"rrryyyrryyyrr\"`\r\n",
    ">\r\n",
    ">输出：`2`\r\n",
    ">\r\n",
    ">解释：调整两次，将中间的两片红叶替换成黄叶，得到 \"rrryyyyyyyyrr\"\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`leaves = \"ryr\"`\r\n",
    ">\r\n",
    ">输出：`0`\r\n",
    ">\r\n",
    ">解释：已符合要求，不需要额外操作\r\n",
    "\r\n",
    "**提示：**\r\n",
    "- `3 <= leaves.length <= 10^5`\r\n",
    "- `leaves` 中只包含字符 `'r'` 和字符 `'y'`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [UlBDOe](https://leetcode.cn/problems/UlBDOe/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [UlBDOe](https://leetcode.cn/problems/UlBDOe/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"rrryyyrryyyrr\"', '\"ryr\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r,ry,ryr=0 if leaves[0]=='r' else 1, float('inf'),float('inf')\n",
    "        for i in range(1,len(leaves)):\n",
    "            if leaves[i]=='r':  r,ry,ryr=r,  min(r,ry)+1, min(ry,ryr)\n",
    "            else: r,ry,ryr=r+1,min(r,ry),min(ry,ryr)+1\n",
    "        return ryr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r, ry, ryr = 1 if leaves[0] == 'y' else 0, float('inf'), float('inf')\n",
    "        for i in range(1, len(leaves)):\n",
    "            if leaves[i] == 'r':\n",
    "                r, ry, ryr = r, min(r, ry) + 1, min(ry, ryr)\n",
    "            else:\n",
    "                r, ry, ryr = r + 1, min(r, ry), min(ry, ryr)+1\n",
    "        return ryr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r, ry, ryr = inf, inf, inf\n",
    "        for c in leaves:\n",
    "            if c == 'r':\n",
    "                r, ry, ryr = 0 if r == inf else r, min(r, ry) + 1, min(ry, ryr)\n",
    "            else:\n",
    "                r, ry, ryr = r + 1 if r != inf else 1, min(r, ry), min(ry, ryr) + 1\n",
    "        return ryr\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        # 进行空间复杂度的优化\n",
    "        n = len(leaves)\n",
    "        dp = [0,0,0]\n",
    "        dp[0] = int(leaves[0] == \"y\")\n",
    "        dp[1] = dp[2] = float(\"inf\")\n",
    "        for i in range(1,n):\n",
    "            isRed = int(leaves[i] == \"r\")\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            a,b,c = dp[0],dp[1],dp[2]\n",
    "            dp[0] = a + isYellow\n",
    "            dp[1] = min(a,b) + isRed\n",
    "            if i>= 2:\n",
    "                dp[2] = min(b,c) + isYellow\n",
    "        return dp[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n=len(leaves)\n",
    "        x,y,z=int(leaves[0]=='y'),float('inf'),float('inf')\n",
    "        for i in range (1,n):\n",
    "            if leaves[i]=='r':\n",
    "                z,y=min(z,y),min(y+1,x+1)\n",
    "            else:\n",
    "                x,y,z=x+1,min(x,y),min(z+1,y+1)\n",
    "        return z\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r, ry, ryr = 1 if leaves[0] == 'y' else 0, float('inf'), float('inf')\n",
    "        for i in range(1, len(leaves)):\n",
    "            if leaves[i] == 'r':\n",
    "                r, ry, ryr = r, min(r, ry) + 1, min(ry, ryr)\n",
    "            else:\n",
    "                r, ry, ryr = r + 1, min(r, ry), min(ry, ryr)+1\n",
    "        return ryr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r,ry,ryr = 1 if leaves[0] =='y' else 0, float('inf'), float('inf')\n",
    "        for i in range(1, len(leaves)):\n",
    "            if leaves[i] == 'r':\n",
    "                r,ry,ryr = r, min(r,ry) + 1, min(ry, ryr)\n",
    "            else:\n",
    "                r, ry, ryr = r+1, min(r, ry), min(ry, ryr) + 1\n",
    "        return ryr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r, ry, ryr = 1 if leaves[0] == 'y' else 0, float(\"inf\"), float(\"inf\")\n",
    "        for i in range(1, len(leaves)):\n",
    "            if leaves[i] == 'r':\n",
    "                # 当前叶子为r时，转换为r, ry, ryr模式\n",
    "                # r:不用转换\n",
    "                # ry:需要将r转换为y，可以在r,ry基础上转换\n",
    "                # ryr:两者模式最小值\n",
    "                r, ry, ryr = r, min(r, ry) + 1, min(ry, ryr)\n",
    "            if leaves[i] == 'y':\n",
    "                r, ry, ryr = r + 1,  min(r, ry), min(ry, ryr) + 1\n",
    "        return ryr\n",
    "    def minimumOperations2(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        changeMap = {'r':'y', 'y':'r'}\n",
    "        def check(s):\n",
    "            stack = []\n",
    "            for c in s:\n",
    "                if stack and stack[-1] == c:\n",
    "                    continue\n",
    "                stack.append(c)\n",
    "            return \"\".join(stack) == 'ryr'\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(curLeaves, i):\n",
    "            if set(curLeaves[i:]) == 'y' or i == n:\n",
    "                if check(curLeaves):\n",
    "                    return 0\n",
    "                return float(\"inf\")\n",
    "            ans = float(\"inf\")\n",
    "            ans = min(ans, dfs(curLeaves, i+1)) # not change\n",
    "            nextLeaves = curLeaves[:i] + changeMap[curLeaves[i]] + curLeaves[i+1:]\n",
    "            ans = min(ans, 1 + dfs(nextLeaves, i+1))\n",
    "            return ans\n",
    "        for i in range(n):\n",
    "            if leaves[i] == 'r':\n",
    "                continue\n",
    "            return dfs(leaves, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        f0, f1, f2 = int(leaves[0] == 'y'), inf, inf \n",
    "        for ch in leaves[1:]:\n",
    "            f0, f1, f2 = f0 + int(ch == 'y'), min(f0, f1) + int(ch == 'r'), min(f1, f2) + int(ch == 'y')\n",
    "        return f2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        g = (1 if leaves[0] == \"y\" else -1)\n",
    "        gmin = g\n",
    "        ans = float(\"inf\")\n",
    "\n",
    "        for i in range(1, n):\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            g += 2 * isYellow - 1\n",
    "            if i != n - 1:\n",
    "                ans = min(ans, gmin - g)\n",
    "            gmin = min(gmin, g)\n",
    "        \n",
    "        return ans + (g + n) // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        r, ry, ryr = 1 if leaves[0] == 'y' else 0, float(\"inf\"), float(\"inf\")\n",
    "        for i in range(1, len(leaves)):\n",
    "            if leaves[i] == 'r':\n",
    "                r, ry, ryr = r, min(r, ry) + 1, min(ry, ryr)\n",
    "            if leaves[i] == 'y':\n",
    "                r, ry, ryr = r + 1,  min(r, ry), min(ry, ryr) + 1\n",
    "        return ryr\n",
    "    def minimumOperations2(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        changeMap = {'r':'y', 'y':'r'}\n",
    "        def check(s):\n",
    "            stack = []\n",
    "            for c in s:\n",
    "                if stack and stack[-1] == c:\n",
    "                    continue\n",
    "                stack.append(c)\n",
    "            return \"\".join(stack) == 'ryr'\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(curLeaves, i):\n",
    "            if set(curLeaves[i:]) == 'y' or i == n:\n",
    "                if check(curLeaves):\n",
    "                    return 0\n",
    "                return float(\"inf\")\n",
    "            ans = float(\"inf\")\n",
    "            ans = min(ans, dfs(curLeaves, i+1)) # not change\n",
    "            nextLeaves = curLeaves[:i] + changeMap[curLeaves[i]] + curLeaves[i+1:]\n",
    "            ans = min(ans, 1 + dfs(nextLeaves, i+1))\n",
    "            return ans\n",
    "        for i in range(n):\n",
    "            if leaves[i] == 'r':\n",
    "                continue\n",
    "            return dfs(leaves, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        def isRed(leave):\n",
    "            return 1 if leave == \"r\" else 0\n",
    "        def isYellow(leave):\n",
    "            return 1 if leave == \"y\" else 0\n",
    "        \n",
    "        dp = [isYellow(leaves[0]), 10**5, 10**5]\n",
    "        for i in range(1, len(leaves)):\n",
    "            temp = [10**5 for _ in range(3)]\n",
    "            temp[0] = dp[0] + isYellow(leaves[i])\n",
    "            temp[1] = min(dp[0], dp[1]) + isRed(leaves[i])\n",
    "            temp[2] = min(dp[1], dp[2]) + isYellow(leaves[i])\n",
    "            dp = temp\n",
    "        return dp[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        # min y[1:i-1] + r[i:j] + y[j+1:n], 2 <= i <= j <= n-1\n",
    "        # min y[i-1] + r[j] - r[i-1] + y[n] - y[j]\n",
    "        # y[n] + min (r[j]-y[j]) - (r[i-1]-y[i-1])\n",
    "        y = []\n",
    "        r = []\n",
    "        for i, x in enumerate(leaves):\n",
    "            if i == 0:\n",
    "                if x == 'y':\n",
    "                    y.append(1)\n",
    "                    r.append(0)\n",
    "                else:\n",
    "                    r.append(1)\n",
    "                    y.append(0)\n",
    "            else:\n",
    "                if x == 'y':\n",
    "                    y.append(y[-1]+1)\n",
    "                    r.append(r[-1])\n",
    "                else:\n",
    "                    r.append(r[-1]+1)\n",
    "                    y.append(y[-1])\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(len(leaves)-1):\n",
    "            if i == 0:\n",
    "                ry = r[i] - y[i]\n",
    "            else:\n",
    "                res = min(res, r[i]-y[i]-ry)\n",
    "                ry = max(ry, r[i]-y[i])\n",
    "        res += y[-1]\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        hong = [-1]* len(leaves)\n",
    "        huang = [-1]* len(leaves)\n",
    "        hong2 = [-1]* len(leaves)\n",
    "        if leaves[0] ==\"y\":\n",
    "            hong[0] = 1\n",
    "        else:\n",
    "            hong[0] = 0\n",
    "\n",
    "        for i in range(1,len(leaves)):\n",
    "            if leaves[i]== \"r\":\n",
    "                hong[i] = hong[i-1]\n",
    "                if huang[i-1] == -1:\n",
    "                    huang[i] = hong[i-1]+1\n",
    "                    continue\n",
    "                else:\n",
    "                    huang[i] = min(huang[i-1],hong[i-1])+1\n",
    "                if hong2[i-1] == -1:\n",
    "                    hong2[i] = huang[i-1]\n",
    "                else:\n",
    "                    hong2[i] = min(huang[i-1],hong2[i-1])\n",
    "            else:\n",
    "                hong[i] = hong[i-1]+1\n",
    "                if huang[i-1] == -1:\n",
    "                    huang[i] = hong[i-1]\n",
    "                    continue\n",
    "                else:\n",
    "                    huang[i] = min(huang[i-1],hong[i-1])\n",
    "                if hong2[i-1] == -1:\n",
    "                    hong2[i] = huang[i-1]+1\n",
    "                else:\n",
    "                    hong2[i] = min(huang[i-1],hong2[i-1])+1\n",
    "        return hong2[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        a=[0 if i=='r' else 1 for i in leaves]\n",
    "        r0=0\n",
    "        b=[0]*len(a)\n",
    "        c=[0]*len(a)\n",
    "        mi=-1\n",
    "        for i in range(len(a)-1,-1,-1):\n",
    "            if a[i]==0:\n",
    "                r0+=1\n",
    "            r=len(a)-i\n",
    "            b[i]=r-2*r0\n",
    "            if mi==-1:\n",
    "                c[i]=1e9\n",
    "            else:\n",
    "                c[i]=r0+b[mi]\n",
    "            if mi==-1 or b[i]<b[mi]:\n",
    "                mi=i\n",
    "        l1=0 \n",
    "        ans=1e9\n",
    "        for i in range(len(a)):\n",
    "            if i>0:\n",
    "                ans=min(ans,l1+c[i])\n",
    "            if a[i]==1:\n",
    "                l1+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "\n",
    "        # rrryyyyrryyyrrryyy\n",
    "        # ryyrrryyrrrryyyyyrryyr\n",
    "        # 1 2 3 2 4 5 2 2 1\n",
    "        # 1 -2 3 -2 4 -5 2 -2 1\n",
    "\n",
    "        # 1 2 3 -2 4 -5 2 -2 1\n",
    "        # 1 -2 -3 -2 4 -5 2 -2 1\n",
    "\n",
    "\n",
    "        op = 0\n",
    "\n",
    "        leaves = list(leaves)\n",
    "        n = len(leaves)\n",
    "        \n",
    "        if leaves[0] == 'y':\n",
    "            leaves[0] = 'r'\n",
    "            op += 1\n",
    "        \n",
    "        if leaves[-1] == 'y':\n",
    "            leaves[-1] = 'r'\n",
    "            op += 1\n",
    "        \n",
    "        if all([l == 'r' for l in leaves]):\n",
    "            op += 1\n",
    "            return op\n",
    "        \n",
    "        # rr = n-1\n",
    "        # while leaves[rr] == 'r':\n",
    "        #     rr -= 1\n",
    "        \n",
    "        # lr = 0\n",
    "        # while leaves[lr] == 'r':\n",
    "        #     lr += 1\n",
    "        \n",
    "        arr = []\n",
    "\n",
    "        cntv = 1\n",
    "        for c in leaves[1:]:\n",
    "            if c == 'r':\n",
    "                if cntv > 0:\n",
    "                    cntv += 1\n",
    "                else:\n",
    "                    arr.append(-cntv)\n",
    "                    cntv = 1\n",
    "            else:\n",
    "                if cntv > 0:\n",
    "                    arr.append(cntv)\n",
    "                    cntv = -1\n",
    "                else:\n",
    "                    cntv -= 1\n",
    "        arr.append(cntv)\n",
    "\n",
    "        #print(leaves)\n",
    "        #print(arr)\n",
    "\n",
    "        dp = {}\n",
    "\n",
    "        # dp[0][i] means in left 'r' the ith pos of arr, the value is the change op numbers\n",
    "        dp[0] = [0] * len(arr)\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        # dp[1][i] measns in middle 'y' the ith pos of arr it convert from dp[0][i-1] or dp[1][i-1]\n",
    "        dp[1] = [0] * len(arr)\n",
    "        dp[1][0] = inf\n",
    "\n",
    "        # d[2][i] measns in right 'r' the ith pos of arr it convert from dp[1][i-1] or dp[2][i-1]\n",
    "        dp[2] = [0] * len(arr)\n",
    "        dp[2][0] = inf\n",
    "\n",
    "\n",
    "        \n",
    "        for i in range(1, len(arr)):\n",
    "            \n",
    "            #print(dp)\n",
    "            #print(arr)\n",
    "            #print(i)\n",
    "            # arr[i] is y\n",
    "            if i % 2 == 1:\n",
    "                dp[0][i] = dp[0][i-1] + arr[i]\n",
    "                dp[1][i] = min(dp[1][i-1], dp[0][i-1])\n",
    "                dp[2][i] = min(dp[2][i-1] + arr[i], dp[1][i-1] + arr[i])\n",
    "\n",
    "            # arr[i] is r\n",
    "            if i % 2 == 0:\n",
    "                dp[0][i] = dp[0][i-1]\n",
    "                dp[1][i] = min(dp[0][i-1] + arr[i], dp[1][i-1] +arr[i])\n",
    "                dp[2][i] = min(dp[1][i-1], dp[2][i-1])\n",
    "\n",
    "        return dp[2][len(arr) - 1] + op\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        dp0 = [0] * len(leaves)\n",
    "        dp1 = [0] * len(leaves)\n",
    "        dp2 = [0] * len(leaves)\n",
    "\n",
    "        # init\n",
    "        dp0[0] = 1 if leaves[0] == 'y' else 0\n",
    "        dp0[1] = dp0[0] + (1 if leaves[1] == 'y' else 0)\n",
    "        dp0[2] = dp0[1] + (1 if leaves[2] == 'y' else 0)\n",
    "        dp1[1] = dp0[0] + (1 if leaves[1] == 'r' else 0)\n",
    "        dp1[2] = min(dp0[1], dp1[1]) + (1 if leaves[2] == 'r' else 0)\n",
    "        dp2[2] = dp1[1] + (1 if leaves[2] == 'y' else 0)\n",
    "\n",
    "        # main func\n",
    "        for i in range(3, len(leaves)):\n",
    "            dp0[i] = dp0[i-1] + (1 if leaves[i] == 'y' else 0)\n",
    "            dp1[i] = min(dp0[i-1], dp1[i-1]) + (1 if leaves[i] == 'r' else 0)\n",
    "            dp2[i] = min(dp1[i-1], dp2[i-1]) + (1 if leaves[i] == 'y' else 0)\n",
    "        \n",
    "        return dp2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        dp0 = [0] * len(leaves)\n",
    "        dp1 = [0] * len(leaves)\n",
    "        dp2 = [0] * len(leaves)\n",
    "\n",
    "        # init\n",
    "        dp0[0] = 1 if leaves[0] == 'y' else 0\n",
    "        dp0[1] = dp0[0] + (1 if leaves[1] == 'y' else 0)\n",
    "        dp0[2] = dp0[1] + (1 if leaves[2] == 'y' else 0)\n",
    "        dp1[1] = dp0[0] + (1 if leaves[1] == 'r' else 0)\n",
    "        dp1[2] = min(dp0[1], dp1[1]) + (1 if leaves[2] == 'r' else 0)\n",
    "        dp2[2] = dp1[1] + (1 if leaves[2] == 'y' else 0)\n",
    "\n",
    "        # main func\n",
    "        for i in range(3, len(leaves)):\n",
    "            dp0[i] = dp0[i-1] + (1 if leaves[i] == 'y' else 0)\n",
    "            dp1[i] = min(dp0[i-1], dp1[i-1]) + (1 if leaves[i] == 'r' else 0)\n",
    "            dp2[i] = min(dp1[i-1], dp2[i-1]) + (1 if leaves[i] == 'y' else 0)\n",
    "        \n",
    "        return dp2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        states = [[0 for i in range(n)] for j in range(3)]\n",
    "        #print(states)\n",
    "        states[1][0] = (inf)\n",
    "        states[2][0] = inf\n",
    "        states[2][1] = inf\n",
    "        states[0][0] = 0 if leaves[0] == 'r' else 1\n",
    "        for i in range(1,n):\n",
    "            red = 1 if leaves[i] == 'r' else 0\n",
    "            \n",
    "            states[0][i] = states[0][i-1] + 1 - red\n",
    "            states[1][i] = min(states[0][i-1],states[1][i-1]) + red\n",
    "            states[2][i] = min(states[1][i-1],states[2][i-1]) + 1 - red\n",
    "        return states[2][n-1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        dp = [[0]*3 for _ in range(n)]\n",
    "        # dp[0][0] = 0 if leaves[0]=='r' else 1\n",
    "        # dp[1][0] = dp[0][0] + (0 if leaves[1]=='r' else 1)\n",
    "        # dp[1][1] = dp[] 0 if leaves[0]=='y' else 1\n",
    "        # dp[2][0] = dp[1][0] + (0 if leaves[2]=='r' else 1)\n",
    "        # dp[2][1] = dp[1][1] + (0 if leaves[0]=='y' else 1)\n",
    "        # dp[2][2] = \n",
    "\n",
    "        dp[0][0] = 0 if leaves[0]=='r' else 1\n",
    "        dp[0][1],dp[0][2] = float('inf'), float('inf')\n",
    "        for i in range(1,n):\n",
    "            if leaves[i] == 'r':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = 1+min(dp[i-1][0], dp[i-1][1])\n",
    "                dp[i][2] = min(dp[i-1][1], dp[i-1][2])\n",
    "            else:\n",
    "                dp[i][0] = 1+dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "                dp[i][2] = 1+min(dp[i-1][1], dp[i-1][2])\n",
    "            pass\n",
    "        return dp[-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        # 定义三种状态，0,1,2。分别表示当前叶子成为左红，黄，右红的操作数\n",
    "        # 注意最开始的边界条件，i=0时，状态1和2是不可能的，所以初始化为inf\n",
    "        n = len(leaves)\n",
    "        dp = [[0]*3 for _ in range(n)]\n",
    "        dp[0][0] = 0 if leaves[0]=='r' else 1\n",
    "        dp[0][1],dp[0][2] = float('inf'), float('inf')\n",
    "        for i in range(1,n):\n",
    "            if leaves[i] == 'r':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = 1+min(dp[i-1][0], dp[i-1][1])\n",
    "                dp[i][2] = min(dp[i-1][1], dp[i-1][2])\n",
    "            else:\n",
    "                dp[i][0] = 1+dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "                dp[i][2] = 1+min(dp[i-1][1], dp[i-1][2])\n",
    "            pass\n",
    "        return dp[-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        f = [[0,0,0] for _ in range(n)]\n",
    "        if leaves[0] == 'y':\n",
    "            f[0][0] = 1\n",
    "        f[0][1] = f[0][2] = f[1][2] = n\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = f[i-1][0]\n",
    "            f[i][1] = min(f[i-1][0], f[i-1][1])\n",
    "            if leaves[i] == 'y':\n",
    "                f[i][0] += 1\n",
    "            else:\n",
    "                f[i][1] += 1\n",
    "            if i >= 2:\n",
    "                f[i][2] = min(f[i-1][1], f[i-1][2]) + (1 if leaves[i] == 'y' else 0)\n",
    "        return f[n-1][2]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n=len(leaves)\n",
    "        BIG=10**10\n",
    "        ldp=[[BIG,BIG] for _ in range(n)]\n",
    "        if leaves[0]=='y':\n",
    "            ldp[0][0]=1\n",
    "        else:\n",
    "            ldp[0][0]=0\n",
    "        for i in range(1,n):\n",
    "            ldp[i][0]=ldp[i-1][0]+int(leaves[i]=='y')\n",
    "            ldp[i][1]=min(ldp[i-1])+int(leaves[i]!='y')\n",
    "        r,y=0,BIG\n",
    "        print(ldp)\n",
    "        if leaves[-1]=='y':\n",
    "            r=1\n",
    "        res=ldp[-2][1]+r\n",
    "        for i in range(n-2,0,-1):\n",
    "            y=min(r,y)+int(leaves[i]!='y')\n",
    "            r+=int(leaves[i]=='y')\n",
    "            res=min(res,min(ldp[i-1])+y,ldp[i-1][1]+r)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        f = [[0] * 3 for _ in range(n)]\n",
    "        left_red, yellow, right_red = 0, 1, 2\n",
    "        f[0][left_red] = 1 if leaves[0] != \"r\" else 0\n",
    "        f[1][left_red] = f[0][left_red] + (1 if leaves[1] != \"r\" else 0)\n",
    "        f[1][yellow] = f[0][left_red] + (1 if leaves[1] != \"y\" else 0)\n",
    "        f[2][left_red] = f[1][left_red] + (1 if leaves[2] != \"r\" else 0)\n",
    "        f[2][yellow] = min(f[1][left_red], f[1][yellow]) + (\n",
    "            1 if leaves[2] != \"y\" else 0\n",
    "        )\n",
    "        f[2][right_red] = f[1][yellow] + (1 if leaves[2] != \"r\" else 0)\n",
    "        for i in range(3, n):\n",
    "            f[i][left_red] = f[i - 1][left_red] + (1 if leaves[i] != \"r\" else 0)\n",
    "            f[i][yellow] = min(f[i - 1][left_red], f[i - 1][yellow]) + (\n",
    "                1 if leaves[i] != \"y\" else 0\n",
    "            )\n",
    "            f[i][right_red] = min(f[i - 1][yellow], f[i - 1][right_red]) + (\n",
    "                1 if leaves[i] != \"r\" else 0\n",
    "            )\n",
    "        return f[n - 1][right_red]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        dp = [[0] * 3 for _ in range(len(leaves))]\n",
    "        dp[0][0] = 0 if leaves[0] == 'r' else 1\n",
    "        dp[0][1] = dp[0][2] = float(\"inf\")\n",
    "        for i in range(1, len(leaves)):\n",
    "            dp[i][0] = dp[i - 1][0] + int(leaves[i] == 'y')\n",
    "            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + int(leaves[i] == 'r')\n",
    "            dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + int(leaves[i] == 'y')\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        demo = [[0,0,0] for _ in range(n)]\n",
    "        demo[0][0] = int(leaves[0] == 'y')\n",
    "        demo[0][1] = demo[0][2] = demo[1][2] = float('inf')\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            demo[i][0] = demo[i-1][0] + int(leaves[i] == 'y')\n",
    "            demo[i][1] = min(demo[i-1][0],demo[i-1][1]) + int(leaves[i] == 'r')\n",
    "            if i > 1:\n",
    "                demo[i][2] = min(demo[i-1][1],demo[i-1][2]) + int(leaves[i] == 'y')\n",
    "        return demo[n-1][2]\n",
    "\n",
    "        \n",
    "            \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "\n",
    "        f = [[0,0,0] for _ in range(n)]\n",
    "        f[0][0] = int(leaves[0] == 'y')\n",
    "        f[0][1] = f[0][2] = f[1][2] = float('inf')\n",
    "\n",
    "        for i in range(1, n):\n",
    "            red = yellow = False\n",
    "            if leaves[i] == 'r':\n",
    "                red = True\n",
    "            else:\n",
    "                yellow = True\n",
    "            \n",
    "            f[i][0] = f[i-1][0] + (1 if yellow else 0)\n",
    "            f[i][1] = min(f[i-1][1], f[i-1][0]) + (1 if red else 0)\n",
    "            if i >= 2:\n",
    "                f[i][2] = min(f[i-1][2], f[i-1][1]) + (1 if yellow else 0)\n",
    "\n",
    "\n",
    "\n",
    "        return f[n-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        # leaves: r(red), y(yellow) -> r y r\n",
    "        # return min(#exchange)\n",
    "        n = len(leaves)\n",
    "        f = [[0, 0, 0] for _ in range(n)]\n",
    "        f[0][0] = int(leaves[0] == \"y\")\n",
    "        f[0][1] = f[0][2] = f[1][2] = float(\"inf\")\n",
    "\n",
    "        for i in range(1, n):\n",
    "            isRed = int(leaves[i] == \"r\")\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            f[i][0] = f[i - 1][0] + isYellow\n",
    "            f[i][1] = min(f[i - 1][0], f[i - 1][1]) + isRed\n",
    "            if i >= 2:\n",
    "                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + isYellow\n",
    "        \n",
    "        return f[n - 1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n=len(leaves)\n",
    "        # dp=[[0,0,0]*n]#dp[i][0],表示状态r,dp[i][1]表示ry，dp[i][2]表示ryr\n",
    "        dp=[[0,0,0] for i in range(n)]\n",
    "        dp[0][0]=int(leaves[0]=='y')#如果初始为y，那么必须调整为人\n",
    "        dp[0][1]=dp[0][2]=dp[1][2]=float('inf')\n",
    "        for i in range(1,n):\n",
    "            is_red=int(leaves[i]=='r')\n",
    "            is_yellow=int(leaves[i]=='y')\n",
    "            dp[i][0]=dp[i-1][0]+is_yellow\n",
    "            dp[i][1]=min(dp[i-1][0]+is_red,dp[i-1][1]+is_red)\n",
    "            if i>=2:\n",
    "                dp[i][2]=min(dp[i-1][1]+is_yellow,dp[i-1][2]+is_yellow)\n",
    "        return dp[n-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        dp = [[0, 0, 0] for _ in range(n)]\n",
    "        dp[0][0] = 0 if leaves[0] == 'r' else 1\n",
    "        dp[0][1] = dp[1][2] =  float('inf')\n",
    "\n",
    "        for i in range(1, n):\n",
    "            isRed    = 1 if leaves[i] == 'r' else 0\n",
    "            isYellow = 1 if leaves[i] == 'y' else 0\n",
    "\n",
    "            dp[i][0] = dp[i-1][0] + isYellow\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + isRed\n",
    "\n",
    "            if i >= 2:\n",
    "                dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + isYellow\n",
    "\n",
    "        return dp[n-1][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        f=[[0,0,0] for _ in range(n)]\n",
    "\n",
    "        f[0][0] = int( leaves[0] == 'y')\n",
    "        f[0][1]= f[0][2] = f[1][2] = float('inf')\n",
    " \n",
    "        for i in range(1,n):\n",
    "            isy = int(leaves[i]=='y')\n",
    "            isr = int(leaves[i]=='r')\n",
    "            f[i][0] = f[i-1][0] + isy\n",
    "            f[i][1] = min(f[i-1][0],f[i-1][1])+isr\n",
    "\n",
    "            if i >= 2:\n",
    "                f[i][2] = min(f[i-1][1],f[i-1][2]) + isy\n",
    "\n",
    "        return f[i][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        f = [[0, 0, 0] for _ in range(n)]\n",
    "        f[0][0] = int(leaves[0] == 'y')\n",
    "        f[0][1] = f[0][2] = f[1][2] = float(\"inf\")\n",
    "        for i in range(1, n):\n",
    "            isRed = int(leaves[i] == \"r\")\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            f[i][0] = f[i - 1][0] + isYellow\n",
    "            f[i][1] = min(f[i - 1][0], f[i - 1][1]) + isRed\n",
    "            if i >= 2:\n",
    "                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + isYellow\n",
    "        return f[n - 1][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n = len(leaves)\n",
    "        dp = [[0, 0, 0] for _ in range(n)]\n",
    "        dp[0][0] = int(leaves[0] == \"y\")\n",
    "        dp[0][1] = dp[0][2] = dp[1][2] = float('inf')\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "            isRed = int(leaves[i] == \"r\")\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            dp[i][0] = dp[i - 1][0] + isYellow\n",
    "            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + isRed\n",
    "\n",
    "            if i >= 2:\n",
    "                dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + isYellow\n",
    "        \n",
    "        return dp[n - 1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        # 参考 926 题\n",
    "        n = len(leaves)\n",
    "        dp = [[0 for _ in range(3)] for _ in range(n)]\n",
    "        dp[0][1] = dp[0][2] = dp[1][2] = inf\n",
    "        dp[0][0] = int(leaves[0] == 'y')\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + int(leaves[i] == 'y')\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + int(leaves[i] == 'r')\n",
    "            if i >= 2:\n",
    "                dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + int(leaves[i] == 'y')\n",
    "        return dp[-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        dp = [[0, 0, 0] for _ in range(n)]\n",
    "        dp[0][0] = int(leaves[0] == \"y\")\n",
    "        dp[0][1] = dp[0][2] = dp[1][2] = float('inf')\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "            isRed = int(leaves[i] == \"r\")\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            dp[i][0] = dp[i - 1][0] + isYellow\n",
    "            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + isRed\n",
    "\n",
    "            if i >= 2:\n",
    "                dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + isYellow\n",
    "        \n",
    "        return dp[n - 1][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        f = [[0, 0, 0] for _ in range(n)]\n",
    "        f[0][0] = int(leaves[0] == \"y\")\n",
    "        f[0][1] = f[0][2] = f[1][2] = float(\"inf\")\n",
    "\n",
    "        for i in range(1, n):\n",
    "            isRed = int(leaves[i] == \"r\")\n",
    "            isYellow = int(leaves[i] == \"y\")\n",
    "            f[i][0] = f[i - 1][0] + isYellow\n",
    "            f[i][1] = min(f[i - 1][0], f[i - 1][1]) + isRed\n",
    "            if i >= 2:\n",
    "                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + isYellow\n",
    "        \n",
    "        return f[n - 1][2]\n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "              \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "        dp[0][0] = int(leaves[0]=='y')\n",
    "        dp[0][1]=dp[0][2]=dp[1][2]=float('inf')\n",
    "\n",
    "        for i in range(1,n):\n",
    "            is_r = int(leaves[i]=='r')\n",
    "            is_y = int(leaves[i]=='y')\n",
    "            dp[i][0] = dp[i-1][0]+is_y\n",
    "            dp[i][1] = min(dp[i-1][0],dp[i-1][1])+is_r\n",
    "            if i >=2:\n",
    "                dp[i][2] = min(dp[i-1][1],dp[i-1][2])+is_y\n",
    "        return dp[n-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, leaves: str) -> int:\n",
    "        n = len(leaves)\n",
    "        # 初始化 dp 数组\n",
    "        dp = [[float('inf')] * 3 for _ in range(n)]\n",
    "        dp[0][0] = 1 if leaves[0] == 'y' else 0\n",
    "        for i in range(1, n):\n",
    "            # 状态转移\n",
    "            dp[i][0] = dp[i-1][0] + (1 if leaves[i] == 'y' else 0)\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + (1 if leaves[i] == 'r' else 0)\n",
    "            if i >= 2:\n",
    "                dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + (1 if leaves[i] == 'y' else 0)\n",
    "        \n",
    "        return dp[n-1][2]\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.minimumOperations(\"rrryyyrryyyrr\"))  # 输出应为2\n",
    "print(sol.minimumOperations(\"ryr\"))  # 输出应为0\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
